﻿using System;
using System.Collections.Generic;
using Lists =Algoritmia.DataStructures.Lists;

using Algoritmia.Utils;
using System.Linq;

namespace Algoritmia.Problems.Sorting
{
    public class MergeSorter<T> : ISorter<T>
    {
        private readonly Func<IEnumerable<T>,Lists.IList<T>> _createList;
        private Comparison<T> _comparison;
        public MergeSorter(Func<IEnumerable<T>, Lists.IList<T>> createList = null)
        {
            _createList = createList ?? (items => AlgoritmiaFactory.Lists<T>.BuildDefault(items));
        }


        private IEnumerable<T> Merge(Lists.IList<T> left, Lists.IList<T> right)
        {
            int i = 0, j = 0;
            while ( i < left.Count && j < right.Count )
            {
                   if ( _comparison(left[i],right[j]) < 0 )
                   {
                       yield return left[i++];
                   }
                   else
                   {
                       yield return right[j++];
                   }
            }

            while (i < left.Count) yield return left[i++];
            while (j < right.Count) yield return right[j++];
        }

        #region ISorter<T> Members

        public IEnumerable<T> Sorted(Lists.IList<T> list, Comparison<T> comparison = null)
        {
            if (list.Count <= 1)
            {
                return list;
            }

            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            var halfCount = list.Count/2;
            var left = _createList(Enumerable.Empty<T>());
            var right = _createList(Enumerable.Empty<T>());
            for (int i = 0; i < halfCount; i++ )
            {
                left.Add(list[i]);
            }

            for (int i = halfCount; i < list.Count; i++ )
            {
                right.Add(list[i]);
            }

            return Merge(_createList(Sorted(left)), _createList(Sorted(right)));
        }

        #endregion
    }

    public class InPlaceMergeSorter<T> : IInPlaceSorter<T>
    {
        protected Comparison<T> _comparison;

        protected virtual void MergeSort(Lists.IList<T> a, int p, int q, Lists.IList<T> c)
        {
            if (q-p > 1)
            {
                MergeSort(a,p,(p+q)/2,c);
                MergeSort(a, (p+q)/2, q, c);
                Merge(a, p, q, c);
            }
        }

        protected void Merge(Lists.IList<T> list, int p, int q, Lists.IList<T> c)
        {
            int mid = (p + q) / 2;
            int i = p,  j = mid, k = p;
           
            while ( i < mid && j < q )
            {
                if ( _comparison(list[i],list[j]) < 0 )
                {
                    c[k++] = list[i++];
                }
                else 
                {
                    c[k++] = list[j++];
                }
            }
            while (i < mid) c[k++] = list[i++];
            while (j < q) c[k++] = list[j++];

            for(i = p; i < q; i++)
            {
                list[i] = c[i];
            }
        }

        #region Implementation of IInPlaceSorter<T>

        public virtual void Sort(Lists.IList<T> list, Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            MergeSort(list, 0, list.Count, Enumerable.Repeat(default(T),list.Count).ToAlgoritmiaList());
            _comparison = null;
        }

        #endregion
    }

    public class ThresholdedInPlaceMergeSorter<T> : InPlaceMergeSorter<T>
    {
        private readonly int _threshold;

        public ThresholdedInPlaceMergeSorter(int threshold)
        {
            _threshold = threshold;
        }

        protected override void MergeSort(Lists.IList<T> a, int p, int q, Lists.IList<T> c)
        {
            if (q - p > _threshold)
            {
                MergeSort(a, p, (p + q)/2, c);
                MergeSort(a, (p + q)/2, q, c);
                Merge(a, p, q, c);
            }
            else
            {
                for (var i = p; i < q; i++)
                {
                    T x = a[i];
                    var j = i - 1;
                    while (j >= 0 && _comparison(x, a[j]) < 0)
                    {
                        a[j + 1] = a[j];
                        j--;
                    }
                    a[j + 1] = x;
                }
   
            }
        }
    }
}
